package oj.oj_CM11;

import oj.ListNode;

/**
 * 链表分割
 * https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking
 */
public class Solution {
    public ListNode partition(ListNode pHead, int x) {
        // write code here
        // 准备两个逻辑上的链表
        // smalList：保存所有小于 x 的结点
        ListNode smallHead=new ListNode();//头结点
        ListNode smallLast=smallHead;//尾结点
        // largeList：保存所有大于等于 x 的结点
        ListNode largeHead=new ListNode();//头结点
        ListNode largeLast=largeHead;//尾结点

        // 遍历链表中每个结点
        ListNode cur=pHead;
        while(cur!=null){
            ListNode curLast=cur.next;
            if(cur.val<x){
                //尾插
                cur.next=null;
                smallLast.next=cur;
                smallLast=cur;
            }else {
                cur.next=null;
                largeLast.next=cur;
                largeLast=cur;
            }
            cur=curLast;
        }

        // 原链表的所有结点都被分到了两条链表中
        smallLast.next=largeHead.next;//结合到一起，跳过smallHead和largeHead,这两个只是工具结点
        return smallHead.next;
    }
}
